package BasicClass.Two;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Two8 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(reader.readLine());
        String[] nums = reader.readLine().split(" ");
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i]=Integer.parseInt(nums[i]);
        }
        Two8 one20 = new Two8();
        one20.heapSort(arr);
        StringBuilder builder = new StringBuilder();
        for (int i : arr) {
            builder.append(i+" ");
        }
        System.out.println(builder);
    }

    /**
     * 给你一个n代表有n个数字，然后你需要使用堆排序将这些数字从小到大排好。
     * @param arr
     * @return
     */
    public void heapSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        // O(N*logN) 适用于后续数据为一个个插入的模式，最后得到一个大根堆
//        for (int i = 0; i < arr.length; i++) {
//            heapInsert(arr,i);
//        }
        // O(N) 适用于直接将所有数据给你的模式(数组排序可以认为如此)，最后得到一个大根堆
        for (int i = arr.length-1; i >= 0; i--) {
            heapify(arr,i,arr.length);
        }
        // O(N*logN)
        int heapSize = arr.length;
        swap(arr,0,--heapSize);
        while (heapSize > 0){// O(N)
            heapify(arr,0,heapSize);// O(logN)
            swap(arr,0,--heapSize);// O(1)
        }
    }

    /**
     * arr[0...index-1]已经是小根堆了，某个数现在处在index位置，往上继续移动
     * arr[o...index]都是小根堆
     * @param arr
     * @param index
     */
    public void heapInsert(int[] arr,int index){
        while (arr[index] > arr[(index-1)/2]){
            swap(arr,index,(index-1)/2);
            index = (index-1)/2;
        }
    }

    /**
     * arr（除index）已经是小根堆了，某个数现在处在index位置，往下继续移动
     * arr都是小根堆
     * @param arr
     * @param index
     */
    public void heapify(int[] arr,int index,int heapsize){
        int left = index*2+1;//左孩子的下标
        while(left < heapsize){
            int largest = left+1<heapsize && arr[left+1] > arr[left]?left+1:left;
            //父和较大的孩子之间，谁的值小，把下标给largest
            largest = arr[index] > arr[largest]?index:largest;
            if(largest == index){
                break;
            }
            swap(arr,largest,index);
            index = largest;
            left = index*2+1;
        }
    }

    public void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
